package ACWing.SearchAndGraphTheory.DFS;
//23. 矩阵中的路径

/**
 * @author :chenjie
 * @date :Created 2022/12/20 20:48
 */
public class PathINMatrix {
    static int n;
    public boolean hasPath(char[][] matrix, String str) {
        n=str.length();
        char[] chars = str.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(dfs(matrix,chars,i,j,0)){
                    return true;
                }
            }
        }
        return false;

    }
    public static boolean dfs(char[][] matrix, char[] str,int x,int y,int m){
        if(matrix[x][y]!=str[m]){//如果不相等放回false
            return false;
        }
        if(m==n-1){//因为源头判断过一次所以只需要判断剩下的便可以
            return true;
        }
        int[]dx={-1,1,0,0};
        int[]dy={0,0,1,-1};
        char t=matrix[x][y];
        matrix[x][y]='*';
        for (int i = 0; i < 4; i++) {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<matrix.length&&b>=0&&b<matrix[a].length){
                if (dfs(matrix,str,a,b,m+1)) {
                    return true;
                }
            }
        }
        matrix[x][y]=t;
        return false;
    }

}
